package 队列;

/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：
 * 完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。
 * 设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
 *
 * CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
 * CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
 * CBTInserter.get_root() 将返回树的根节点。
 *
 * 示例 1：
 *
 * 输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
 * 输出：[null,1,[1,2]]
 *
 */
public class 往完全二叉树添加节点 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class CBTInserter {
        TreeNode root;
        private Queue<TreeNode> queue;
        public CBTInserter(TreeNode root) {
            this.root = root;
            queue = new LinkedList<>();
            queue.offer(root);
        }

        public int insert(int v) {
            TreeNode nxt = new TreeNode(v);
            while(queue.peek().left != null && queue.peek().right != null) {
                TreeNode node = queue.poll();
                queue.offer(node.left);
                queue.offer(node.right);
            }
            TreeNode peek = queue.peek();
            if(peek.left == null) {
                peek.left = nxt;
                return peek.val;
            }
            peek.right = nxt;
            return peek.val;
        }

        public TreeNode get_root() {
            return root;
        }
    }
}
